//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 示例 3： 
//
// 
//输入：s = "a"
//输出："a"
// 
//
// 示例 4： 
//
// 
//输入：s = "ac"
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母（大写和/或小写）组成 
// 
// Related Topics 字符串 动态规划 
// 👍 3712 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

public class LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new LongestPalindromicSubstring().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 二维动态规划问题
        // 转移方程是 dp[i][j] = dp[i + 1][j - 1]，因此遍历顺序需要从左下角开始，故i从n-1开始，j从i开始
      public String longestPalindrome(String s) {
            int n = s.length();
            if (n == 1) {
                return s;
            }
            boolean[][] dp = new boolean[n][n];
            int maxLen = 0;
            String res ="";

            for (int i = n - 1; i >= 0; i--) {
                for (int j = i ; j < n; j++) {
                    if (i==j){
                        dp[i][i] = true;
                    }
                    else if (j - i == 1) {
                        dp[i][j] = s.charAt(j) == s.charAt(i);
                    } else if (s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                    if (dp[i][j] && j + 1 - i >= maxLen) {
                        maxLen = j + 1 - i;
                        res = s.substring(i, j + 1);
                    }
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}